import json

with open('topo.json') as data_file:
    data = json.load(data_file)

def get_switch_type(datapath_id):
    return data["switch"][datapath_id]["switch-type"]

def get_next_hop_id(datapath_id, port_no):
    return data["switch"][datapath_id]["ports"][port_no][0]

def get_link_id(datapath_id, port_no):
    return data["switch"][datapath_id]["ports"][port_no][1]

def get_pod_id(mac_addr):
    return data["pod"][mac_addr]


# 1. get_near_link
# 2. build_graph
# 3. get_path

# link_id ==> int
def get_near_link(link_id):
    ret = set()
    for dpid, switch in data['switch'].items():
        is_find = False
        for port_no, port in switch['ports'].items():
            if len(port) == 2 and int(port[1]) == link_id:
                is_find = True
                break
        if is_find:
            for port_no, port in switch['ports'].items():
                if len(port) == 2 and int(port[1]) != link_id:
                    ret.add(port[1])
    return list(ret)


def build_graph():
    graph = {}
    for dpid, switch in data['switch'].items():
        for port_no, port in switch['ports'].items():
            if len(port) == 1:
                continue
            graph[port[1]] = {
                "visit":False,
                "next":get_near_link(int(port[1]))
            }
    return graph

# link_src, link_dest ==> str
def get_path(link_src, link_dest):
    queue = []
    queue.append(link_src)
    prev = {}
    prev[link_src] = None
    graph = build_graph()
    graph[link_src]['visit'] = True
    print graph
    is_find = False
    for link in queue:
        print link
        for near_link in graph[link]['next']:
            if graph[near_link]['visit'] == False and prev[link] != near_link:
                graph[near_link]['visit'] = True
                prev[near_link] = link
                queue.append(near_link)
            if near_link == link_dest:
                is_find = True
                break
        if is_find:
            break

    path = []
    link = link_dest
    while link is not None:
        path.append(prev[link])
        link = prev[link]
    return path[:-2]
    